//有限状态机
#ifndef FSM_H_
#define FSM_H_

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <stack>

using namespace std;

struct FSM_Node {
    //定义
    int id;
    set<int> old{};
    int state;
    map<set<char>, vector<FSM_Node *>> trans = {}; //定义状态图
    bool isEndState;

    //构造函数
    FSM_Node(int id, int state, bool isEndState) : id(id), state(state), isEndState(isEndState) {}
};

class FSM {
private:
    int num{};
    set<set<char>> charList;
    vector<FSM_Node *> nodes;
    map<int, FSM_Node *> index = {};
    FSM_Node *first{}; //first node

public:
    FSM() = default;

    ~FSM() = default;

    explicit FSM(set<set<char>> charList);

    void addNode(FSM_Node *node);

    void addTrans(int from, int to, const set<char>& chSet);

    FSM_Node *getFirst();

    FSM_Node *getNode(int id);

    int getNum() const;

    void printFSM();

    set<set<char>> getCharList();
};

FSM createNFA();

FSM NFAtoDFA(FSM NFA);

FSM minimizeDFA(FSM DFA);

int identify(FSM DFA, string token);

#endif
